//1795.[java单源最短路径Dijkstra优先队列BFS邻接矩阵]最佳路径  https://oj.rnd.huawei.com/problems/1795/details
// 给定单板间的有向连接关系：如单板101到单板102存在连接，权值为10，
// 其连接关系描述为：101 102 10; 单板102到单板101存在连接，权值为6，其连接关系描述为：102 101 6。
// 基于单板间的有向连接关系，从起始单板到目的单板可能有0或多条可达的有向路径，
// 某条路径权值是该路径上各连接的权值之和。
// 给定多组格式为起始单板 目的单板的查询命令，请依次计算并返回其最佳路径权值；
// 若某条最佳路径不存在，则该条最佳路径权值返回-1。
// 最佳路径的规则如下：经过的连接个数最少；
// 若符合规则 1 的路径存在多条，选择权值最小的；
// Dijkstra 算法是(Single Source Shortest Path) 问题的算法，
// 但它有一个巨大的限制：只能用于没有权重为负的边的图。
// 若符合规则 1 的路径存在多条，选择权值最小的；(节点最少，权值最小)
//输入 2 2
//100 101 10
//102 101 5
//100 101
//102 100
//输出 10
//-1
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


public class Main {
	
    private static class Path implements Comparable<Path> {
        int curBoard;
        int count;
        int weight;
        Path(int curBoard, int count, int weight) {
            this.count = count;
            this.curBoard = curBoard;
            this.weight = weight;
        }
        @Override
        public int compareTo(Path other) {
            if (this.count != other.count) {
                return this.count - other.count;
            }
			return this.weight - other.weight;
        }
    }
	
    static final class Connection {
        int srcBoard;
        int snkBoard;
        int weight;
        Connection(int srcBoard, int snkBoard, int weight) {
            this.srcBoard = srcBoard;
            this.snkBoard = snkBoard;
            this.weight = weight;
        }
    }
    static final class BoardPair {
        int srcBoard;
        int snkBoard;
        BoardPair(int srcBoard, int snkBoard) {
            this.srcBoard = srcBoard;
            this.snkBoard = snkBoard;
        }
    }
    // 待实现函数，在此函数中填入答题代码
    private static Integer getBestRoute(BoardPair boardPair, List<Connection> connectionsList) {
        Queue<Path> queue = new PriorityQueue<>();
        List<int[]>[] board = new List[1000];        // SrcBoard  -   <snkBoard, weight>
        boolean[][] visited = new boolean[1000][1000];  // visited :   src - snk 
        for (int i = 0; i < board.length; i++) {
            board[i] = new ArrayList<>();
        }
        for (Connection conn : connectionsList) {
            if (conn.srcBoard == boardPair.srcBoard) {
                queue.offer(new Path(conn.snkBoard, 1, conn.weight));   // 队列进 snkBoard 
                visited[conn.srcBoard][conn.snkBoard] = true;
            }
            board[conn.srcBoard].add(new int[] {conn.snkBoard, conn.weight});
        }
        int[] res = new int[] {Integer.MAX_VALUE, Integer.MAX_VALUE};    // {数量,权重}
        while (!queue.isEmpty()) {
            Path nd = queue.poll();    // 队列出
            int count = nd.count;
            if (count > res[0]) {     // 数量
                break;
            }
            int weight = nd.weight;
            int curBoard = nd.curBoard;
            if (boardPair.snkBoard == curBoard) {   // 到达, 更新最近路径和权重
                if (res[0] > count) {
                    res[0] = count;
                    res[1] = weight;
                } else if (res[0] == count) {
                    res[1] = Math.min(res[1], weight);
                }
            }
            for (int[] next : board[curBoard]) {    // 遍历 board 之后的全部路径
                if (!visited[curBoard][next[0]]) {   // 未访问的进队列
                    queue.offer(new Path(next[0], count + 1, weight + next[1]));
                    visited[curBoard][next[0]] = true;
                }
            }
        }
        if (res[1] != Integer.MAX_VALUE) {
            return res[1];
        } else {
            return -1;
        }
    }

    
    /**
     * main入口由OJ平台调用
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int nRow = cin.nextInt();
        int mRow = cin.nextInt();
        List<Connection> connectionsList = new ArrayList<>();
        for (int i = 0; i < nRow; i++) {
            int srcBoard = cin.nextInt();
            int destBoard = cin.nextInt();
            int weight = cin.nextInt();
            connectionsList.add(new Connection(srcBoard, destBoard, weight));
        }
        List<BoardPair> boardsList = new ArrayList<>();
        for (int i = 0; i < mRow; i++) {
            int srcBoard = cin.nextInt();
            int destBoard = cin.nextInt();
            boardsList.add(new BoardPair(srcBoard, destBoard));
        }
        cin.close();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < boardsList.size(); i++) {
            result.add(getBestRoute(boardsList.get(i), connectionsList));
        }
        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }
    }
}


